#ifndef SUFIX_WORD_H
#define SUFIX_WORD_H

#include "classical-problems.h"
#include <string.h>
#include <stdlib.h>
#include <algorithm>

#include "str_utils.h"

namespace pot {
class SufixWords {
public:
  SufixWords(int n) : seq_(NULL), words_(NULL), n_chars_(0), n_words_(0),
                      words_capacity_(0), char_capacity_(0), k_(0) {
    words_ = new char*[n];
    words_capacity_ = n;
    seq_ = new char[10 * n];
    char_capacity_ = 10 * n;
  }

  ~SufixWords() {
    if (NULL != seq_) delete[] seq_;
    if (NULL != words_) delete[] words_;
    words_capacity_ = 0;
    char_capacity_ = 0;
  }

  bool Load(const char *filename);

  void Initialize(int k) {
    k_ = k;
    for (int i = 0; i < k; ++i) words_[n_words_][i] = 0;
    std::sort(words_, words_ + n_words_, WordsCmp(k));
  }

  void Generate(int n);

  void Print() { this->Output(stdout); }

  void Save(const char *filename) {
    FILE *fp = fopen(filename, "w");
    if (NULL == fp) {
      printf("can't open %s\n", filename);
      return;
    }
    this->Output(fp);
    fclose(fp);
  }

private:
  void Output(FILE *fp);

private:
  char *seq_;
  int n_chars_;
  char **words_;
  int n_words_;
  int k_;
  int words_capacity_;
  int char_capacity_;

  static const int kMaxWordLength = 20;
};

bool SufixWords::Load(const char *filename) {
  FILE *fp = fopen(filename, "r");
  if (NULL == fp) {
    printf("can't open %s\n", filename);
    return false;
  }

  words_[0] = seq_;
  while (n_words_ < words_capacity_ && 
         n_chars_ + kMaxWordLength < char_capacity_ &&
         fscanf(fp, "%s", words_[n_words_]) != EOF) {
    n_chars_ += strlen(words_[n_words_]) + 1;
    words_[++n_words_] = seq_ + n_chars_; 
  }
  fclose(fp);

  return true;
}

void SufixWords::Generate(int n) {
  char *phrase = seq_;
  for (int words_left = n; words_left > 0; --words_left) {
    int l = -1;
    int u = n_words_;
    while (l + 1 != u) {
      int m = (l + u) / 2;      
      if (wordncmp(words_[m], phrase, k_) < 0) {
        l = m;
      }
      else { 
        // this can ensure that u points to the beginning of 'phrase's
        u = m;
      }
    }
    char *p = NULL;
    for (int i = 0; wordncmp(phrase, words_[u+i], k_) == 0; ++i) {
      if ((rand() % (i + 1)) == 0) p = words_[u + i];
    }

    phrase = skip(p, 1);
    if (strlen(skip(phrase, k_ - 1)) == 0) break;
    printf("%s ", skip(phrase, k_ - 1));
  }
  printf("\n***************************************\n");
}

void SufixWords::Output(FILE *fp) {
  for (int i = 0; i < n_words_; ++i) {
    fprintf(fp, "word[%d]:", i); 
    char *p = words_[i];
    for (int j = 0; j <= k_; ++j) {
      fprintf(fp, " %s", p);
      p += strlen(p) + 1;
    }
    fprintf(fp, "\n");
  }
}

class SufixArray {
public:
  SufixArray(int n) : seq_(NULL), sufix_(NULL), n_(0), capacity_(0) {
    seq_ = new char[n + 1];
    sufix_ = new char*[n + 1];
    capacity_ = n;
  }
  ~SufixArray() {
    if (NULL != seq_) delete[] seq_;
    if (NULL != sufix_) delete[] sufix_;
    capacity_ = 0;
  }

  bool Load(const char *filename); 

  void MaxCommonSubStr();  

  bool FindSubStr(const char *str);

  void Print() { this->Output(stdout); }

  void Save(const char *filename) {
    FILE *fp = fopen(filename, "w");
    if (NULL == fp) {
      printf("can't open %s\n", filename);
      return;
    }
    this->Output(fp);
    fclose(fp);
  }
  
private:
  void Output(FILE *fp) {
    for (int i = 0; i < n_; ++i) {
      fprintf(fp, "[%d]:%s\n", i, sufix_[i]);
    }
  }

private:
  char *seq_;
  char **sufix_;
  int n_;
  int capacity_;
};

bool StrCmp(const char *p, const char *q) {  
  return strcmp(p, q) < 0;
}

bool SufixArray::Load(const char *filename) {
  FILE *fp = fopen(filename, "r");
  if (NULL == fp) {
    printf("can't open %s\n", filename);
    return false;
  }
  sufix_[0] = seq_;
  while (n_ < capacity_ && fscanf(fp, "%c", sufix_[n_]) != EOF) {
    ++n_;
    sufix_[n_] = seq_ + n_;
  }
  seq_[n_] = '\0';
  fclose(fp);

  std::sort(sufix_, sufix_ + n_, StrCmp);
  return true;
}

int MaxCommonLen(const char *p, const char *q) {
  int len = 0;
  
  while (*p != '\0' && *q != '\0' && p[len] == q[len]) ++len;

  return len;
}

void SufixArray::MaxCommonSubStr() {
  int max_common_len = 0;
  char *str = NULL;
  for (int i = 0; i < n_ - 1; ++i) {
    int len = MaxCommonLen(sufix_[i], sufix_[i + 1]);
    if (len > max_common_len) {
      max_common_len = len;
      str = sufix_[i];
    }
  }
  printf("[max common substring]:");

  char tmp = str[max_common_len];
  str[max_common_len] = '\0';
  printf("%s\n", str);
  str[max_common_len] = tmp;
}

bool SufixArray::FindSubStr(const char *str) {
  int l = -1, u = n_;
  int len = strlen(str);
  while (l + 1 != u) {
    int m = (l + u) / 2;
    int ret = strncmp(sufix_[m], str, len);
    if (ret < 0)  l = m;
    else if (ret > 0) u = m;
    else return true;
  }
  return false;
}

/*
 * word[i] is the beginning of the i-th sufix words group
 * sufix words is sorted on the k-words comparation
 */
void SufixWordTest() { 
  SufixWords words(100000);
  if (!words.Load("input.txt")) return;

  for (int k = 1; k < 5; ++k) {
    words.Initialize(k);
    words.Save("output.txt");
    words.Generate(100);
  }

  pot::SufixArray arr(100000);
  if (!arr.Load("input.txt")) return;
  arr.Save("arr.txt");
  arr.MaxCommonSubStr();
  const char *strs[] = { "hello", "Future", "number " };
  for (int i = 0; i < 3; ++i) {
    if (arr.FindSubStr(strs[i])) {
      printf("find '%s'\n", strs[i]);
    }
    else {
      printf("can't find '%s'\n", strs[i]);
    }
  }
}
} // pot

#endif // SUFIX_WORD_H
